package lib

//和240一样
func init() {
	Probs = append(Probs, Problem{
		Num:         74,
		Discription: "搜索二维有序矩阵",
		Level:       2,
		Labels: map[string]int{
			"二分查找":  1,
            "分界查找":  1,
			"矩阵": 1,
		},
	})
}

func SearchMatrix(matrix [][]int, target int) bool {
    left:=0
    right:=len(matrix)-1
	//先根据每一行的第0列二分搜索
    for left<=right{
        mid:=(left+right)/2
        if target<matrix[mid][0]{
            right=mid-1
        }else{
            left=mid+1
        }
    }

	//注意要保证结果必须要<=target
    var column int
    if left==len(matrix)||matrix[left][0]>target{
        column=left-1
    }else{
        column=left
    }
	//考虑搜索出来小于0的情况（target比matrix[0][0]还小）
    if column<0{
        return false
    }

    left=0
    right=len(matrix[0])-1
    for left<=right{
        mid:=(left+right)/2
        if matrix[column][mid]==target{
            return true
        }
        if matrix[column][mid]>target{
            right=mid-1
        }else{
            left=mid+1
        }
    }

    return false 
}